Manually Translating C to Cyclone

To a first approximation, you can port a simple program from C to Cyclone by following these steps which are detailed below:

Even when you follow these suggestions, you’ll still need to test and debug your code carefully. By far, the most common run-time errors you will get are uncaught exceptions for null-pointer dereference or array out-of-bounds. Under Linux, you should get a stack backtrace when you have an uncaught exception which will help narrow down where and why the exception occurred. On other architectures, you can use gdb to find the problem. The most effective way to do this is to set a breakpoint on the routines _throw_null() and _throw_arraybounds() which are defined in the runtime and used whenever a null-check or array-bounds-check fails. Then you can use gdb’s backtrace facility to see where the problem occurred. Of course, you’ll be debugging at the C level, so you’ll want to use the -save-c and -g options when compiling your code.

Change pointer types to fat pointer types where necessary

Ideally, you should examine the code and use thin pointers (e.g., int* or better int *@notnull) wherever possible as these require fewer run-time checks and less storage. However, recall that thin pointers do not support pointer arithmetic. In those situations, you’ll need to use fat pointers (e.g., int *@fat which can also be written as int?). A particularly simple strategy when porting C code is to just change all pointers to fat pointers. The code is then more likely to compile, but will have greater overhead. After changing to use all fat pointers, you may wish to profile or reexamine your code and figure out where you can profitably use thin pointers.

Be careful with char pointers. By default, a char ? is treated as zero-terminated, i.e. a char * @fat @zeroterm. If you are using the char pointer as a buffer of bytes, then you may actually wish to change it to be a char ? @nozeroterm instead. Along these lines, you have to be careful that when you are using arrays that get promoted to pointers, that you correctly indicate the size of the array to account for the zero terminator. For example, say your original C code was

    char line[MAXLINELEN];
    while (fgets(line, MAXLINELEN, stdin)) ...

If you want your pointer to be zero-terminated, you would have to do the following:

    char line[MAXLINELEN+1] @zeroterm;
    while (fgets(line, MAXLINELEN, stdin)) ...

The @zeroterm qualifier is needed since char arrays are not zero-terminated by default. Adding the +1 makes space for the extra zero terminator that Cyclone includes, ensuring that it won’t be overwritten by fgets. If you don’t do this, you could well get an array bounds exception at runtime. If you don’t want your char array to be zero-terminated, you can simply leave the original C code as is.

Use comprehensions to heap-allocate arrays

Cyclone provides limited support for malloc and separated initialization but this really only works for bits-only objects. To heap- or region-allocate and initialize an array that might contain pointers, use new or rnew in conjunction with array comprehensions. For example, to copy a vector of integers s, one might write:

  int *@fat t = new {for i < numelts(s) : s[i]};

Use tagged unions for unions with pointers

Cyclone only lets you read members of unions that contain “bits” (i.e., ints; chars; shorts; floats; doubles; or tuples, structs, unions, or arrays of bits.) So if you have a C union with a pointer type in it, you’ll have to code around it. One way is to simply use a @tagged union. Note that this adds hidden tag and associated checks to ensure safety.

Initialize variables

Top-level variables must be initialized in Cyclone, and in many situations, local variables must be initialized. Sometimes, this will force you to change the type of the variable so that you can construct an appropriate initial value. For instance, suppose you have the following declarations at top-level:

struct DICT; 
struct DICT *@notnull new_dict();
struct DICT *@notnull d;
void init() {
  d = new_dict();
}

Here, we have an abstract type for dictionaries (struct Dict), a constructor function (new_dict()) which returns a pointer to a new dictionary, and a top-level variable (d) which is meant to hold a pointer to a dictionary. The init function ensures that d is initialized. However, Cyclone would complain that d is not initialized because init may not be called, or it may only be called after d is already used. Furthermore, the only way to initialize d is to call the constructor, and such an expression is not a valid top-level initializer. The solution is to declare d as a “possibly-null” pointer to a dictionary and initialize it with NULL:

struct DICT; 
struct DICT *nonnull new_dict();
struct DICT *d;
void init() {
  d = new_dict();
}

Of course, now whenever you use d, either you or the compiler will have to check that it is not NULL.

Put breaks or fallthrus in switch cases

Cyclone requires that you either break, return, continue, throw an exception, or explicitly fallthru in each case of a switch.

Replace one temporary with multiple temporaries

Consider the following code: 

void foo(char * x, char * y) {
  char * temp;
  temp = x;
  bar(temp);
  temp = y;
  bar(temp);
}

When compiled, Cyclone generates an error message like this: 

type mismatch: char *@zeroterm #0  != char *@zeroterm #1

The problem is that Cyclone thinks that x and y might point into different regions (which it named #0 and #1 respectively), and the variable temp is assigned both the value of x and the value of y. Thus, there is no single region that we can say temp points into. The solution in this case is to use two different temporaries for the two different purposes:

void foo(char * x, char * y) {
  char * temp1;
  char * temp2;
  temp1 = x;
  bar(temp1);
  temp2 = y;
  bar(temp2);
}

Now Cyclone can figure out that temp1 is a pointer into the region #0 whereas temp2 is a pointer into region #1.

Connect argument and result pointers with the same region

Remember that Cyclone assumes that pointer inputs to a function might point into distinct regions, and that output pointers, by default point into the heap. Obviously, this won’t always be the case. Consider the following code:

int *foo(int *x, int *y, int b) {
  if (b)
    return x;
  else
    return y;
}

Cyclone complains when we compile this code: 

foo.cyc:3: returns value of type int *`GR0 but requires int *
  `GR0 and `H are not compatible. 
foo.cyc:5: returns value of type int *`GR1 but requires int *
  `GR1 and `H are not compatible.

The problem is that neither x nor y is a pointer into the heap. You can fix this problem by putting in explicit regions to connect the arguments and the result. For instance, we might write:

int *`r foo(int *`r x, int *`r y, int b) {
  if (b)
    return x;
  else
    return y;
}

and then the code will compile. Of course, any caller to this function must now ensure that the arguments are in the same region.

Insert type information to direct the type-checker

Cyclone is usually good about inferring types. But sometimes, it has too many options and picks the wrong type. A good example is the following:

void foo(int b) {
  printf("b is %s", b ? "true" : "false");
}

When compiled, Cyclone warns: 

(2:39-2:40): implicit cast to shorter array

The problem is that the string “true” is assigned the type const char ?{5} whereas the string “false” is assigned the type const char ?{6}. (Remember that string constants have an implicit 0 at the end.) The type-checker needs to find a single type for both since we don’t know whether b will come out true or false and conditional expressions require the same type for either case. There are at least two ways that the types of the strings can be promoted to a unifying type. One way is to promote both to char? which would be ideal. Unfortunately, Cyclone has chosen another way, and promoted the longer string (“false”) to a shorter string type, namely const char ?{5}. This makes the two types the same, but is not at all what we want, for when the procedure is called with false, the routine will print

b is fals

Fortunately, the warning indicates that there might be a problem. The solution in this case is to explicitly cast at least one of the two values to const char ?:

void foo(int b) {
  printf("b is %s", b ? ((const char ?)"true") : "false");
}

Alternatively, you can declare a temp with the right type and use it:

void foo(int b) {
  const char ? t = b ? "true" : "false"
  printf("b is %s", t);
}

The point is that by giving Cyclone more type information, you can get it to do the right sorts of promotions. Other sorts of type information you might provide include region annotations (as outlined above), pointer qualifiers, and casts.

Copy “const” code or values to make it non-const

Cyclone takes const seriously. C does not. Occasionally, this will bite you, but more often than not, it will save you from a core dump. For instance, the following code will seg fault on most machines:

void foo() {
  char ?x = "howdy"
  x[0] = 'a';
}

The problem is that the string “howdy” will be placed in the read-only text segment, and thus trying to write to it will cause a fault. Fortunately, Cyclone complains that you’re trying to initialize a non-const variable with a const value so this problem doesn’t occur in Cyclone. If you really want to initialize x with this value, then you’ll need to copy the string, say using the dup function from the string library:

void foo() {
  char ?x = strdup("howdy");
  x[0] = 'a';
}

Now consider the following call to the strtoul code in the standard library:

extern unsigned long strtoul(const char ?`r n, 
                             const char ?`r*`r2 endptr,
                             int base);
unsigned long foo() {
  char ?x = strdup("howdy");
  char ?*e = NULL;
  return strtoul(x,e,0);
}

Here, the problem is that we’re passing non-const values to the library function, even though it demands const values. Usually, that’s okay, as const char ? is a super-type of char ?. But in this case, we’re passing as the endptr a pointer to a char ?, and it is not the case that const char ?* is a super-type of char ?*. In this case, you have two options: Either make x and e const, or copy the code for strtoul and make a version that doesn’t have const in the prototype.

Get rid of calls to free, calloc, etc.

There are many standard functions that Cyclone can’t support and still maintain type-safety. An obvious one is free() which releases memory. Let the garbage collector free the object for you, or use region-allocation if you’re scared of the collector. Other operations, such as memset, memcpy, and realloc are supported, but in a limited fashion in order to preserve type safety.

Use polymorphism or tagged unions to get rid of void*

Often you’ll find C code that uses void* to simulate polymorphism. A typical example is something like swap:

void swap(void **x, void **y) {
  void *t = x;
  x = y;
  y = t;
}

In Cyclone, this code should type-check but you won’t be able to use it in many cases. The reason is that while void* is a super-type of just about any pointer type, it’s not the case that void** is a super-type of a pointer to a pointer type. In this case, the solution is to use Cyclone’s polymorphism:

void swap(`a *x, `a *y) {
  `a t = x;
  x = y;
  y = t;
}

Now the code can (safely) be called with any two (compatible) pointer types. This trick works well as long as you only need to “cast up” from a fixed type to an abstract one. It doesn’t work when you need to “cast down” again. For example, consider the following:

int foo(int x, void *y) {
  if (x)
   return *((int *)y);
  else {
    printf("%s\n",(char *)y);
    return -1;
  }
}

The coder intends for y to either be an int pointer or a string, depending upon the value of x. If x is true, then y is supposed to be an int pointer, and otherwise, it’s supposed to be a string. In either case, you have to put in a cast from void* to the appropriate type, and obviously, there’s nothing preventing someone from passing in bogus cominations of x and y. The solution in Cyclone is to use a tagged union to represent the dependency and get rid of the variable x:

@tagged union IntOrString { 
  int Int;
  const char *@fat String;
};
typedef union IntOrString i_or_s;
int foo(i_or_s y) {
  switch (y) {
  case {.Int = i}:  return i;
  case {.String = s}:  
    printf("%s\n",s);
    return -1;
  }
}

Rewrite the bodies of vararg functions

See Varargs for more details.

Use exceptions instead of setjmp

Many uses of setjmp/longjmp can be replaced with a try-block and a throw. Of course, you can’t do this for things like a user-level threads package, but rather, only for those situations where you’re trying to “pop-out” of a deeply nested set of function calls.